package offer.offer02;

import java.util.Stack;

/**
 * 万万没想到是可以中间带个null的, 长什么样都可以的二叉树
 * 上面的解法只能适用于完全二叉树
 * 这里使用非完全二叉树, 没办法使用数组作为中间载体, 直接通过List<TreeNode>来实现镜像;
 *
 * 对于镜像这种随意的二叉树, 应该根本没有办法把树一维化;
 * 想了一下, 镜像问题, 就是把每一个节点的左右节点互换, 对于下面两种方法,
 * 使用栈和使用递归, 并没有区别, 栈相当于是先序遍历整个树, 把每个节点的左右子树交换,
 * 栈应该只能用于先序遍历, 但是递归的话可以做到实现中序或者后序, 实际上并没有区别;
 */
public class S27二叉树的镜像III {
    //栈
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        //Stack是接口, 直接创建接口对象???
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
    //递归
    public TreeNode mirrorTree2(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode leftRoot = mirrorTree(root.right);
        TreeNode rightRoot = mirrorTree(root.left);
        root.left = leftRoot;
        root.right = rightRoot;
        return root;
    }
}
